package 普通数组.最大子数和;
/**
 * 题目描述
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 力扣链接：https://leetcode-cn.com/problems/maximum-subarray/
 * 力扣题：53
 * */
/**
 * 题目思路
 * 暴力解法：
 * 双城far循环
 * 第一层判断从哪里遍历它的子数组
 * 第二层遍历子数组并且累加每个子数组中的元素
 * 比较出来最大的一个子数组的和
 * 但是时间复杂度太高
 * 操出时间
 * */

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE; // 初始化最小值

        // 枚举每一个数组
        for(int i = 0;i < n;i++){
            int currentSum = 0; //当前子数组的和
            for(int j = i;j < n;j++){
                currentSum += nums[j];// 累加当前子数组的元素
                maxSum = Math.max(maxSum,currentSum); // 更新最大和
            }
        }
        return maxSum; // 返回最大子数组的和
    }
    public static void main(String[] args){
        Solution solution = new Solution();
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(solution.maxSubArray(nums));
    }
}